"""
https://leetcode.cn/problems/sum-root-to-leaf-numbers/description/

129. 求根节点到叶节点数字之和
已解答
中等
相关标签
相关企业
给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

 

示例 1：


输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25
示例 2：


输入：root = [4,9,0,5,1]
输出：1026
解释：
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026
 

提示：

树中节点的数目在范围 [1, 1000] 内
0 <= Node.val <= 9
树的深度不超过 10
"""
# Definition for a binary tree node.


from typing import List, Optional


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree_node(nums:List[int])->Optional[TreeNode]:
    if len(nums)==0:
        return None
    root=TreeNode(nums[0])
    
    # 构建TreeNode
    queue = [root]
    i = 1
    while i < len(nums):
        current = queue.pop(0)
        if nums[i] is not None:
            current.left = TreeNode(nums[i])
            queue.append(current.left)
        i += 1
        if i < len(nums) and nums[i] is not None:
            current.right = TreeNode(nums[i])
            queue.append(current.right)
        i += 1
    return root




class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        # 考虑使用递归,先收集到各项根节点的数字,再统一求和
        def itr_node(node)->List[List[int]]:
            if not node:
                return []
            if not node.left and not node.right:
                return [[node.val]]
            res=[]
        
            left_res=itr_node(node.left)
            if left_res:
                for link_vals in left_res:
                    res.append([node.val]+link_vals)
            right_res=itr_node(node.right)
            if right_res:
                for link_vals in right_res:
                    res.append([node.val]+link_vals)
            return res
        
        def calc_sum(arr:List[int])->int:
            sum=0
            for i in arr:
                sum=i+sum*10
            return sum
        
        res_arr=itr_node(root)
        num_arr=[calc_sum(_) for _ in res_arr]
        return sum(num_arr)
        pass

if __name__=='__main__':
    arr=[4,9,0,5,1]
    root=build_tree_node(arr)
    s=Solution()
    res=s.sumNumbers(root)
    print(res)